import java.util.*;

/**
 * 51. N 皇后
 * https://leetcode-cn.com/problems/n-queens/
 */
public class Solutions_51 {
    public static void main(String[] args) {
        int n = 4;
        // output: {{".Q..", "...Q", "Q...", "..Q."}, {"..Q.", "Q...", "...Q", ".Q.."}}

        List<List<String>> result = solveNQueens(n);
        System.out.println(result);
    }

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        Set<Integer> columns = new HashSet<>();
        Set<Integer> mainDiagonal = new HashSet<>();
        Set<Integer> secondDiagonal = new HashSet<>();
        backtrack(res, queens, 0, columns, mainDiagonal, secondDiagonal);
        return res;
    }

    public static void backtrack(List<List<String>> res, int[] queens, int row,
                                 Set<Integer> columns, Set<Integer> mainDiagonal,
                                 Set<Integer> secondDiagonal) {
        // 结束条件
        if (row == queens.length) {
            List<String> board = generateBoard(queens);
            res.add(board);
            return;
        }
        for (int i = 0; i < queens.length; i++) {
            if (columns.contains(i)) {
                // i 列上已存在
                continue;
            }
            // 两坐标，若在同一主斜线上，那么行列之差相等
            int diagonal1 = row - i;
            if (mainDiagonal.contains(diagonal1)) {
                // [row, i] 坐标的主对角线上已存在
                continue;
            }
            // 两坐标，若在同一副斜线上，那么行列之和相等
            int diagonal2 = row + i;
            if (secondDiagonal.contains(diagonal2)) {
                // [row, i] 坐标的副对角线上已存在
                continue;
            }
            queens[row] = i;
            columns.add(i);
            mainDiagonal.add(row - i);
            secondDiagonal.add(row + i);
            // 下一行，“皇后”的位置
            backtrack(res, queens, row + 1, columns, mainDiagonal, secondDiagonal);
            // 回溯，当前位置还原
            columns.remove(i);
            mainDiagonal.remove(row - i);
            secondDiagonal.remove(row + i);
        }
    }

    public static List<String> generateBoard(int[] queens) {
        List<String> board = new ArrayList<>();
        int count = queens.length;
        for (int i = 0; i < queens.length; i++) {
            char[] arr = new char[count];
            Arrays.fill(arr, '.');
            int col = queens[i];
            // 第 i 行上，皇后所在列
            arr[col] = 'Q';
            board.add(String.valueOf(arr));
        }
        return board;
    }
}
